package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * 排序算法的稳定性测试
 * 
 * @author 付大石
 */

public class Main {

    public static void main(String[] args) {

        String[] arr = new String[] { "QWE", "ASD", "SDF", "EBW", "GDF", "SDG", "XCV", "WER", "DFH", "XCV", "ASD",
                "QWE", "AXC", "QWE", "ZXC", "TYU", "BDF", "WEFXVH", "JSF", "SF", "ERH", "SFGHT", "BSFG", "RSTHS",
                "SFHJ", "SRTH", "SBDF", "SRG", "A", "SDFWEX", "DFGSDF", "DFGR", "EERT", "RTB", "RTY", "HEF", "NYR",
                "UIU" };

        Comparator<String> comp = new MyComparator();
        sort(arr,comp);
        System.out.println(Arrays.toString(arr));
    }

    private static <T> void sort(T[] arr, Comparator<T> comp) {
        sort(arr, 0, arr.length - 1, comp);
    }

    private static <T> void sort(T[] arr, int low, int high, Comparator<T> comp) {

        if (high <= low) {
            return;
        }
        int p = partition(arr, low, high, comp);
        sort(arr, low, p - 1, comp);
        sort(arr, p + 1, high, comp);
    }

    private static <T> int partition(T[] arr, int low, int high, Comparator<T> comp) {

        T p = arr[low]; // 切分元素
        while (low < high) {
            while (low < high && comp.compare(p, arr[high]) < 0) {
                high--;
            }
            if (low < high) {
                arr[low] = arr[high];
                low++;
            }
            while (low < high && comp.compare(p, arr[low]) > 0) {
                low++;
            }
            if (low < high) {
                arr[high] = arr[low];
                high--;
            }
        }
        arr[low] = p;
        return low;
    }
}

class MyComparator implements Comparator<String> {

    private Map<Character, Integer> map;

    public MyComparator() {
        map = new HashMap<>();
        map.put('R', 0);
        map.put('W', 1);
        map.put('Q', 2);
        map.put('O', 3);
        map.put('J', 4);
        map.put('M', 5);
        map.put('V', 6);
        map.put('A', 7);
        map.put('H', 8);
        map.put('B', 9);
        map.put('S', 10);
        map.put('G', 11);
        map.put('Z', 12);
        map.put('X', 13);
        map.put('N', 14);
        map.put('T', 15);
        map.put('C', 16);
        map.put('I', 17);
        map.put('E', 18);
        map.put('K', 19);
        map.put('U', 20);
        map.put('P', 21);
        map.put('D', 22);
        map.put('Y', 23);
        map.put('F', 24);
        map.put('L', 25);
    }

    @Override
    public int compare(String s1, String s2) {

        int lim = Math.min(s1.length(), s2.length());
        for (int i = 0; i < lim; i++) {
            int i1 = map.get(s1.charAt(i));
            int i2 = map.get(s2.charAt(i));
            if (i1 != i2) {
                return i1 - i2;
            }
        }
        return s1.length() - s2.length();
    }

}